package _11_整理题目._3_字符串_递归_dfs_bfs_双指针;

import org.apache.commons.lang.text.StrBuilder;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/restore-ip-addresses/
 *
 * 给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。
 * 你可以按任何顺序返回答案。
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 *
 * 思路：由于需要复原所有的 ip，可以使用 dfs
 *      终止条件1，segId == 4
 *      终止条件2，segStart == s.length
 *
 */
public class _04_数字字符串复原IP地址 {
    
    private int[] segments = new int[4];
    List<String> ans = new ArrayList<>();
    
    public List<String> restoreIpAddresses(String s) {
        dfs(s, 0, 0);
        return ans;
    }
    
    public void dfs(String s, int segId, int segStart) {
        // 终止条件：
        if (segId == 4) {
            if (segStart == s.length()) {
                StrBuilder sb = new StrBuilder();
                for (int i = 0; i < 4; i++) {
                    sb.append(segments[i]);
                    if (i != 3) {
                        sb.append(".");
                    }
                }
                ans.add(sb.toString());
            }
            return;
        }
        if (segId == s.length()) return;
        
        // 当前 segStart == '0'，只能解析为 0，并 dfs
        if (s.charAt(segStart) == '0') {
            segments[segId] = 0;
            dfs(s, segId+1, segStart+1);
        }
        // 正常解析当前 ip，并 dfs
        int addr = 0;
        for (int segEnd = segStart; segEnd < s.length(); segEnd++) {
            addr = addr*10 + (s.charAt(segEnd)-'0');
            if (addr > 0 && addr <= 255) {
                segments[segId] = addr;
                dfs(s, segId+1, segEnd+1);
            } else {
                break;
            }
        }
    }
    
    @Test
    public void main() {
        String s = "25525511135";
        System.out.println(restoreIpAddresses(s));
        assert 0xff==255;
    }
}
